package algorithm.greedy.basic;

import java.util.Arrays;

/**
 * 项目名称: god
 * 包 名 称: algorithm.greedy.basic
 * 类 名 称: Coin
 * 类 描 述: TODO
 * 创建时间: 2020/7/13 8:42 上午
 * 创 建 人: Justice
 * 假如有25分 20分 5分 1分的硬币
 * 现在需要找给客户41分的零钱
 * 如何办到硬币个数最少
 */
public class Coin {
    public static void test(Integer[] faces, int money) {
        Arrays.sort(faces);
        int coins = 0;
        int index = faces.length - 1;
        while (index >= 0) {
            while (money >= faces[index]) {
                System.out.println(faces[index]);
                money -= faces[index];
                coins++;
            }
            index--;
        }
        System.out.println("所需要硬币数" + coins);
    }

    public static void test1(Integer[] faces, int money) {
        Arrays.sort(faces);
        int coins = 0;
        for (int i = faces.length - 1; i >= 0; i--) {
            if (money < faces[i]) {
                continue;
            }
            System.out.println(faces[i]);
            money -= faces[i];
            coins++;
            i = faces.length;
        }
        System.out.println("所需要硬币数" + coins);
    }

    public static void test2(Integer[] faces, int money) {
        Arrays.sort(faces, (Integer f1, Integer f2) -> f2 - f1);
        int coins = 0;
        int i = 0;
        while (i < faces.length) {
            if (money < faces[i]) {
                i++;
                continue;
            }
            System.out.println(faces[i]);
            money -= faces[i];
            coins++;
        }
        System.out.println("所需要硬币数" + coins);
    }
}
